# 线性查找 顺序查找 O(n)
li = [1, 3, 4, 23, 6, 2, 8, 17]
print(6 in li)
li.index(6)
# 可以查找无序列表和有序列表，所以在系统中是使用的顺序查找

'******************************************************************'

# 二分查找 对最高位和最低位进行标记，比切片二分省内存
# 不可以对无序列表进行查找
# O(logn)
def bin_search(li, val):
    low = 0
    high = len(li) - 1
    while low <= high:  # 只要候选区不空就继续循环
        mid = (low + high) // 2
        if li[mid] == val:
            return mid
        elif li[mid] < val:
            low = mid + 1
        else:  # li[mid] > val
            high = mid - 1
    # return 'NONE'


li = [1, 2, 3, 5, 7, 12, 43, 52, 100]

print(bin_search(li, 100))
